package com.LeetCode.why19;

public class RemoveNthNodeFromEndOfList {
    //题目要求：Try to do this in one pass.（一趟完成）
    //充分理解“倒数第n”的解决方案！！
    //Discuss给力！！
    //倒数第n + 剩余长度gap = 总长度
    //倒数第n也就是正数第gap
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution1 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            //自己想法的答案
            ListNode p = head;
            ListNode number = head;
            int no = 0;
            while (number != null) {
                no++;
                number = number.next;
            }
            if (no - n == 0) {
                p = p.next;
                return p;
            }
            for (int i = 1; i < no - n; i++) {
                p = p.next;
            }
            ListNode tmp = p.next;
            p.next = tmp.next;
            return head;
        }
    }

    class Solution2 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            //Discussion想法的答案
            //注意链表，只能删除下一个结点，不能回退（单链表）！所以注意找准待删点！
            ListNode start = new ListNode(0xffff);
            start.next = head;
            ListNode first = start;
            ListNode second = start;
            for (int i = 1; i <= n; i++) {
                first = first.next;
            }
            while (first.next != null) {
                first = first.next;
                second = second.next;
            }
            ListNode tmp = second.next;
            second.next = tmp.next;
            return start.next;
        }
    }
}
